<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>希尔排序</title>
</head>

<body>
    <script>
        // 时间复杂度 O（n^2）
        function inserSort(unordArr, n, d) { //n为一次分组后该组第一个成员的索引
            for (let i = n + d; i < unordArr.length; i += d) { //i为j的下一个元素
                let num = unordArr[i]
                let j = i - d
                while (j >= 0 && unordArr[j] > num) {
                    unordArr[j + d] = unordArr[j]
                    j -= d
                }
                unordArr[j + d] = num
            }
            // console.log(unordArr);
            return unordArr
        }
        //   dn为数组长度除以二向下取整
        //第n次分组后插入排序的第一个元素为一直到dn（不包含索引为dn），第二个元素与第一个元素间隔dn
        function shellSort(arr) {
            let d = Math.floor(arr.length / 2)
            while (d >= 1) {
                for (let n = 0; n < d; n++) { //每次分组都要进行好几次插入排序
                    inserSort(arr, n, d)
                    console.log(arr);
                }
                d = Math.floor(d / 2)
            }
            // console.log(arr);
        }
        shellSort([5, 7, 4, 6, 3, 1, 2, 9, 8])
    </script>
</body>

</html>